package com.leetcode.array;

import java.util.ArrayList;
import java.util.List;

/**
 * 78. 子集 Subsets
 * @ClassName Subsets
 * @Description 我是一个注释
 * @Author HaiziGe
 * @Date 2018/11/3 17:25
 * @Version 1.0
 **/
public class Subsets {

    /**
     * 方法一   免去递归的方法
     * 第一次获得[] 加入1获得 [1]
     * 第二次获得[],[1] 加入2 获得 [2],[1,2]
     * 第三次获得[],[1],[2],[1,2] 加入3获得[3],[1,3],[2,3],[1,2,3]
     * 最终获得 [],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]
     * @param nums
     * @return
     */
    public List<List<Integer>> subsets1(int[] nums) {

        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());
        for(int n : nums){
            int size = result.size();
            for(int i=0; i<size; i++){
                List<Integer> subset = new ArrayList<>(result.get(i));
                subset.add(n);
                result.add(subset);
            }
        }
        return result;
    }

    /**
     * 方法二 递归的方法
     * @param nums
     * @return
     */
    public List<List<Integer>> subsets2(int[] nums) {
        List<List<Integer>> res=new ArrayList<>();
        backtrack(res,new ArrayList<>(),nums,0);
        return res;
    }

    private void backtrack(List<List<Integer>> res,List<Integer> tempList,int[] nums,int start){
        res.add(new ArrayList<>(tempList));
        for(int i=start;i<nums.length;i++){
            tempList.add(nums[i]);
            backtrack(res,tempList,nums,i+1);
            tempList.remove(tempList.size()-1);
        }
    }

}
